{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c27c4204",
   "metadata": {},
   "source": [
    "# 二分查找\n",
    "\n",
    "二分查找困难的点在于，当数组的个数为偶数时，左右区间如何划分？\n",
    "\n",
    "假设现在数组的元素为`[5, 7, 7, 8, 8, 10]`，第一次二分后，中值取在$M = \\frac{0+5}{2}=2.5=2$的位置，也就是第二个7。\n",
    "\n",
    "由于L和R都是闭区间，即指向的元素被包含在当前的子数组内。所以，二分之后L和R也都应该包含在闭区间里。\n",
    "\n",
    "所以此时$L=M+1$，下一个区间为$[M+1, R]$。\n",
    "\n",
    "**终止条件**：`L > R` \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1559d02",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lower_bound(self, nums: List[int], target: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1  # 闭区间[left, right]\n",
    "        while left <= right:\n",
    "            mid = int((left + right) / 2)\n",
    "            # 注意此处必须是大于等于【记公式】\n",
    "            if nums[mid] >= target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def higher_bound(self, nums: List[int], target: int) -> List[int]:\n",
    "        # <=x = (>x) - 1 = (>=(x + 1)) - 1\n",
    "        # 由于是小于等于，所以只可能向下越界\n",
    "        return self.lower_bound(nums=nums, target=target + 1) - 1\n",
    "\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        start = self.lower_bound(nums=nums, target=target)\n",
    "        # target比数组中所有数都大 或者 数组中不包含target\n",
    "        if start == len(nums) or nums[start] != target:\n",
    "            return [-1, -1]\n",
    "        end = self.higher_bound(nums=nums, target=target)\n",
    "        if end == -1 or nums[end] != target:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return [start, end]\n",
    "\n",
    "\n",
    "sol = Solution()\n",
    "print(sol.searchRange([5, 7, 7, 8, 8, 10], 8))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tmp",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
